package com.xk._02算法篇._04recrusion;

import com.xk.tools.Times;

/**
 * @description: 楼梯有 n 阶台阶，上楼可以一步上 1 阶，也可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法？
 * @author: xu
 * @date: 2022/10/15 22:12
 */
public class ClimbStairs {
    public static void main(String[] args) {
        ClimbStairs climb = new ClimbStairs();
        Times.test("climb0", () -> System.out.println(climb.climbStairs0(10)));
        Times.test("climb1", () -> System.out.println(climb.climbStairs1(10)));
    }

    public int climbStairs0(int n) {
        if (n <= 2) return n;
        return climbStairs0(n-1) + climbStairs0(n-2);
    }

    // 时间：O(n) 空间：O(1) 非递归
    public int climbStairs1(int n) {
        if (n <= 2) return n;
        int first = 1, second = 2;
        while (n-- >= 3){
            second = first + second;
            first = second - first;
        }
        return second;
    }
}
